블로그에 관하여
해결된 문제
어제 밤부터 오늘 새벽동안 새롭게 추가한 기능이 있다. 댓글 기능인데, 블로그라 하면 댓글도 있는 편이 좋다고 생각해서 기능을 넣게 되었다. Github App중에 utterances라는 기능이 있는데, Repository에서 Issue라는 것을 생성하는 방식으로 댓글 기능을 지원한다고 한다.
Github의 Issue는 프로젝트의 기획, 작업, 개선 사항, 버그 수정, 새로 추가될 기능 등 모든 것을 가리키는 용어라고 한다. Github에서는 이 모든 활동에 대해 Issue를 등록하고, 그것을 기반으로 작업을 진행할 수 있다고 한다.1 이러한 이슈를 모종의 방법으로 각 포스팅 별로 생성할 수 있고, 이를 댓글로 활용하는 기능인 것 같았다. 첫 댓글이 달리는 날이 기대된다.
블로그에 대한 문제점은 어제 작성한 내용에서 3번째 항목을 제외하고는 그대로 남아있다. 빠른 시일내에 공식 문서들을 읽어보는 것이 좋겠다. 블로그에 관한 이야기는 여기까지 하고, B-Tree의 Search가 어떤 식으로 동작하는지 이야기 해보겠다.
B-Tree 프로젝트
오늘은 B-Tree에서 특정 키값을 찾는 Search에 대해서 이야기 하도록 하겠다. 어제와 마찬가지로, Wikipedia2를 기준으로 설명하겠다.
B-Tree의 Search
B-Tree에서 Search는 이름 그대로 특정 키 값이 트리 내부에 존재하는지 검사하는 동작으로, Binary Search Tree에서 키 값을 찾는 방식과 유사하게 작동한다. 루트 노드에서 시작하여 트리는 재귀적으로 위에서 아래로 내려가는 방향으로 탐색을 진행한다. 각 레벨에서, 탐색 범위에 맞는 subtree로 탐색의 범위를 좁혀간다. 어떤 subtree의 범위는 부모 노드에 포함된 어떤 값들이나 키들로 정의된다.
그게 무슨 소리니…
설명만 읽어봐서는 정확히 무슨 말인지 이해하기 어려울 것이다. 그래서 직접 B-Tree에서 특정한 값을 탐색하는 예시를 통해 앞서 설명한 내용들을 다시 풀어서 설명할 것이다.
예시
아래 그림과 같은 B-Tree를 생각해보자.
이 B-Tree는 order가 $3$인 B-Tree이며, 총 26개의 키가 저장되어 있다. 이 B-Tree에서 8, 13, 27을 탐색하는 과정을 알아보겠다.
앞서 설명한 B-Tree에서 Search가 작동하는 방식은 다음과 같은 단계로 구분할 수 있다.
- 전체 트리의 루트 노드에서 탐색을 시작한다.
- 탐색 범위에 맞는 subtree를 선택한다.
- 선택된 subtree의 루트 노드에서 2단계부터 진행한다.
이제 각 키들을 찾는 과정을 따라가보겠다.
1. B-Tree에서 8을 Search 하기
우선 루트 노드인 $(9, 18)$ 노드에서 탐색을 시작한다. 찾으려 하는 키값인 $8$은 루트 노드의 첫 번째 키값인 $9$보다 작으므로, 왼쪽 subtree에서 탐색을 이어간다.
다음은 $(3, 6)$에서 탐색을 이어간다. 찾고자 하는 키값인 $8$은 현재 노드의 마지막 키값인 $6$보다 크므로, 오른쪽 subtree에서 탐색을 이어간다.
현재 노드에서 우리가 찾고 있던 키값인 $8$을 확인할 수 있다. 이 트리에는 $8$이 존재한다는 사실을 확인할 수 있다.
2. B-Tree에서 13을 Search 하기
우선 루트 노드인 $(9, 18)$ 노드에서 탐색을 시작한다. 찾으려 하는 키값인 $13$은 루트 노드의 첫 번째 키값인 $9$보다 크고, ‘두 번째’ 키값인 $18$보다 작으므로, 가운데 subtree에서 탐색을 이어간다.
다음은 $(12, 15)$ 노드에서 탐색을 이어간다. 찾고자 하는 키값인 $13$은 현재 노드의 첫 번째 키값인 $12$보다 크고, ‘두 번째’ 키값인 $15$보다 작으므로, 가운데 subtree에서 탐색을 이어간다.
현재 노드에서 우리가 찾고 있던 키값인 $13$을 확인할 수 있다. 이 트리에는 $13$이 존재한다는 사실을 확인할 수 있다.
3. B-Tree에서 27을 Search 하기
우선 루트 노드인 $(9, 18)$ 노드에서 탐색을 시작한다. 찾으려 하는 키값인 $27$은 루트 노드의 마지막 키값인 $18$보다 크므로, 오른쪽 subtree에서 탐색을 이어간다.
다음은 $(21, 24)$ 노드에서 탐색을 이어간다. 찾고자 하는 키값인 $27$은 현재 노드의 마지막 키값인 $24$보다 크므로, 오른쪽 subtree에서 탐색을 이어간다.
현재 $(25, 26)$ 노드에는 $27$이 존재하지 않는다. 그러나 이 노드는 리프 노드이기 때문에 더 이상 탐색을 진행할 수 없고, 이 B-Tree에는 $27$이 존재하지 않는다는 사실을 확인할 수 있다.
오늘은 여기까지
오늘은 B-Tree에서 Search가 무엇인지, 어떻게 작동하는지 알아보았다. 내일은 B-Tree에서 어떤 키값을 Insert하는 방법에 대해서 알아보도록 하겠다. 또한, 새로운 키값을 Insert하는 과정에서 발생하는 여러 가지 상황에 대해서도 알아볼 것이다.
마무리
오늘은 여기서 글을 마무리 하겠다. 별로 잡담할만한 거리가 떠오르지 않아 오늘은 생략하겠다.
오늘의 개발은 여기까지!
1: velog 링크
2: https://en.wikipedia.org/wiki/B-tree